%!TexProgram=xelatex
%\documentclass[a4paper]{article}
\documentclass[a4paper]{ctexart}
\usepackage{xltxtra}
\usepackage{listings}
\usepackage{float}
\usepackage{graphicx}
\usepackage{geometry}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{enumitem}
\geometry{a4paper,scale=0.75}
\title{二叉树项目报告}
\author{周川迪}
\begin{document}
\maketitle
\section{设计思路}
\subsection{增加基础虚类}
增加了一个基础虚类:BinaryTree，作为最顶级的基类，用以规范全部二叉树的基本操作;

全部二叉树的基本操作可以认为是三种遍历:前序遍历，中序遍历和后续遍历.把这三种操作、析构函数和isEmpty() const作为二叉树抽象类的纯虚函数.将子类中private里的printTree改名为printInOrder，因为在这四种树中，printTree的本质都是中序遍历.

其他的函数在不同的子类中，有的有const修饰而有的并没有.因此不作为纯虚函数.

\subsection{继承关系}
BinarySearchTree(BST)派生自BinaryTree（二叉树）.BST在二叉树的基础上添加了一些附加的特性，以支持较高效的搜索、插入和删除操作.

在一般的BST和AvlTree的关系中，AvlTree通常被认为是BST的一种特殊形式.AvlTree是一种自平衡的二叉搜索树，通过在插入或删除节点的过程中进行旋转操作，保持树的平衡性，确保树的高度始终较小，从而提高查找、插入和删除等操作的效率.

RedBlackTree（红黑树）是一种特定类型的自平衡二叉搜索树，其平衡条件相对于AvlTree更弱.

SplayTree派生于BST以利用BST的基本结构，通过对节点的旋转操作来实现SplayTree的自适应特性。这种继承关系使得SplayTree在具有二叉搜索树的基础上，通过旋转操作提高了对访问频繁节点的访问效率。

\subsection{Node之间的关系}

所有的Node都是二叉树的节点(包括AvlNode、RedBlackNode)，因此统一命名为BinaryNode,放在各类的protected类型中.（各类中原本的private改成了protected，使子类可以进行访问.）但是额外要考虑AvlTree和RedBlackTree中的Node的额外结构。



\section{测试代码}
我创建了TestTree.cpp以测试我的代码，参考了教师程序中的内容.该测试程序用于测试我实现的所有树数据结构的功能和正确性.我进行了变量名上的调整，防止变量名冲突，确保每个测试部分都有独立的变量.同时用简陋的分隔线区分了不同树的测试结果.此外，还改了部分参数以测试printTree函数的结果.最终每个树结构的测试结果都显示无误.



\end{document}



\end{document}